Section: New Results

Network distance analysis

We addressed the diameter computation problem in the case of undirected unweighted graphs, where the diameter $D$ is defined as the maximum distance among all the pairs of nodes and the distance $d(u,v)$ between two nodes $u$ and $v$ is defined as the number of edges contained in the shortest path from $u$ to $v$. In the context of real-world networks, the textbook method based on performing a breadth-first search (in short, bfs ) from every node of the graph, requires a prohibitive cost of $O\left(nm\right)$ time, where $n$ is the number of nodes and $m$ is the number of edges of the graph. Our main contribution consists of showing that bfs can indeed be an extremely powerful tool to compute the exact value of the diameter, whenever it is used in a more clever way. In particular, we have developed the iterative Fringe Upper Bound (in short, $i$fub ) algorithm to calculate the exact value of the diameter. This work has been accepted for publication in Theoretical Computer Science (to appear).

We then successively generalised the idea of the $i$fub algorithm, by presenting the directed $i$fub (in short, d $i$fub ) algorithm, in order to calculate the diameter of the strongly connected components of directed graphs [33] . As far as we know, d $i$fub is the first algorithm which is able to compute exactly the diameter of the strongly connected components of huge real-world directed graphs. The d $i$fub algorithm can also return a pair of nodes whose distance is exactly equal to the diameter, and a natural adaptation of it works also for weighted graphs.